Triangle Drawing: Calculating the Deltas - Part 2

By Statix

This is just a little follow up to my last tute which explained how to calculate the increments needed to shade a gouraud shaded triangle. I used a fairly hands on point of view, but didn't give people the lovely mathematical derivation. A couple of people asked about it - so here it is. And no, I didn't just pull the equations out of the air! Here it all is, in vector maths. You'll probably need a small bit of A levelish maths / 3d coding experience, you have been warned... (but not much) Here goes...

The trick is a little bit of mathematical sideways thinking. All you need to know is a bit of vector maths. First, what have we got? we've got 3 X coordinates (on the screen), 3 Y coordinates (on the screen as well) and 3 shade values for gouraud shading. That's three 2d vectors (x and y), and three numbers (shades), right?

well, yes, but what happens if we think about it as three 3d vectors: x,y and instead of z, the shade. You can now imagine a 3d space, with the triangle screen coordinates specifying x and y (I think of that as a position along the flat plane, like a table top) and the shade values specifying a height above the table top for each corner of the triangle. Don't get confused about this shade / height as being anything to do with your original 3d world in the 3d engine. This is a made-up mathematical 3d world where gouraud-shades are being used as the third dimension. As far as your gouraud shader is concerned, you're drawing 2d triangles on a screen. We've added the third dimension: shade.

Anyway, back to our triangle. There it is, floating in our 3d x-y-shade space, defined by its three 3d corners. As we all know, a triangle uniquely defines an infinite plane - the one it lies in (that's what is so cool about triangles after all). Let's write down the equation of the plane:

(equation 1)
ax + by + cz + d = 0

All points in 3d space which satisfy this equation lie on the plane where our triangle is. So, all the triangle points also satisfy this equation (by definition). But what are a,b,c,d? We have to work them out. The derivation is quite easy, and is in most A Level maths texts. Basically, [a,b,c] are the normal to the plane (as a vector), and d is the perpendicular distance from the origin to the plane. Don't worry too much about what that means...

Every 3d programmer knows how to find a normal. You can use a cross product. At this point I am going to use vector notation - that is, if we call the 3 vectors representing the corners of our triangleas V1, V2, V3 (capitals for vectors) and N for the normal vector to the triangle / plane (so N = [a,b,c]) we have:

(equation 2)
N = (V2 - V1) ^ (V3 - V1)

^ is the cross product and that was the classic normal calculation code. You've all seen and coded it a thousand times before right? Right.

Right, now we know a,b,c it's really easy to find d as well just by rearranging equation 1 like this:

(equation 3)
d = -ax - by - cz

We know of a,b,c are components of N, which we just worked out and we can plug in any values of x,y,z which lie on the plane (such as one of the corners of the triangle - V1, V2 or V3. Doesn't matter which - you get the same answer).

Right, now we've found a,b,c AND d. Well that's it. You've worked out the increments. REALLY you say? well look at this rearrangement of equation 1:

(equation 4)
z = (-d - ax - by) / c

Remember that z in ourweirdo3d space, represents gouraud shade value. So NOW we've got an equation which tells us what shade value to draw, at ANY pixel position on the screen (given by x and y) - including all the pixels inside the triangle. That's it! equation 4 is all you need. To refer back to my last text, "c" here is the same as "area" in the last text. The x_inc and y_inc values I calculated are in fact -a/c (ooh, spooky) and each time you go down the screen (y increases by one), z (= shade) increases by -b/c. So there you have it.

Hope that made sense.
Cheers!

Statix

http://ban.joh.cam.ac.uk/~alex
For all my demos, the source code for bleam, and graphic design stuff.....